package datastructure.book.tujiesuanfa.list.solution._1_easy;

import datastructure.book.tujiesuanfa.list.bean.ListNode;
import datastructure.book.tujiesuanfa.list.bean.Node;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;

public class Solution1 {

    @Test
    public void testReverseBookList(){
        ListNode listNode4 = new ListNode(1);
        ListNode listNode3 = new ListNode(4,listNode4);
        ListNode listNode2 = new ListNode(6,listNode3);
        ListNode listNode1 = new ListNode(3,listNode2);
        System.out.println(Arrays.toString(reverseBookList(listNode1)));
        System.out.println(Arrays.toString(reverseBookList2(listNode1)));
    }

    /**
     * 倒序返回这个链表
     * 示例：
     * 输入：head = [3,6,4,1]
     * 输出：[1,4,6,3]
     * 0 <= 链表长度 <= 10000
     */
    public int[] reverseBookList(ListNode head) {
        ArrayList<Integer> integers = new ArrayList<>();
        if (head == null) {
            return new int[0];
        }
        integers.add(head.val);
        ListNode temp = head.next;
        while (temp != null) {
            integers.add(temp.val);
            temp = temp.next;
        }
        int[] result = new int[integers.size()];
        for (int i = 0; i < integers.size(); i++) {
            result[i] = integers.get(integers.size()-1-i);
        }
        return result;
    }
    public int[] reverseBookList2(ListNode head) {
        if (head == null) {
            return new int[0];
        }
        int count = 0;
        ListNode temp = head;
        while (temp != null) {
            count++;
            temp = temp.next;
        }
        int[] result = new int[count];
        ListNode temp2 = head;
        int index = count-1;
        while (temp2 != null) {
            result[index] = temp2.val;
            temp2 = temp2.next;
            index--;
        }
        return result;
    }

    /**
     * 给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
     * 返回删除后的链表的头节点。
     * 给定的头指针就是链表的第一个元素，链表中节点的值互不相同
     */
    public ListNode deleteNode(ListNode head, int val) {
        if (head != null && head.val == val) {
            ListNode result = head.next;
            head.next = null;
            return result;
        }
        ListNode temp = head;
        while (temp != null && temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
                break;
            } else {
                temp = temp.next;
            }
        }
        return head;
    }

    /**
     * 给定一个头节点为 head 的单链表，倒序返回链表
     */
    public ListNode trainningPlan(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = head;
        ListNode pre = null;
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 给定一个头节点为 head 的链表，请查找并返回倒数第 cnt 个节点。
     * 1 <= cnt <= head.length
     * 例如：
     * 输入：head = [2,4,7,8], cnt = 1
     * 输出：8
     */
    public ListNode trainingPlan(ListNode head, int cnt) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode result = head;
        int count = 1;
        while (head.next != null) {
            head = head.next;
            count++;
        }
        int loopCount = count - cnt;
        for (int i = 0; i < loopCount; i++) {
            result = result.next;
        }
        return result;
    }

    /**
     * 给定两升序链表 l1、l2，请升序合并这两个链表并返回。
     * 新链表是通过拼接给定的两个链表的所有节点组成的
     * 输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]
     * 输入：l1 = [], l2 = [] 输出：[]
     * 输入：l1 = [], l2 = [0] 输出：[0]
     */
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return l1;
        }
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode result;
        ListNode pre;
        if (l1.val <= l2.val) {
            result = l1;
            pre = l1;
            l1 = l1.next;
        } else {
            result = l2;
            pre = l2;
            l2 = l2.next;
            while (l2 != null && l2.val < l1.val) {
                pre = l2;
                l2 = l2.next;
            }
            pre.next = l1;
            if (l2 == null) {
                return result;
            }
            pre = pre.next;
            l1 = l1.next;
        }
        while (true) {
            if (l1 == null) {
                pre.next = l2;
                break;
            }
            if (l2 == null) {
                pre.next = l1;
                break;
            }
            if (l1.val <= l2.val) {
                pre.next = l1;
                pre = pre.next;
                l1 = l1.next;
            } else {
                pre.next = l2;
                pre = pre.next;
                l2 = l2.next;
            }
        }
        return result;
    }

    /**
     * 找两链表交点，如果两个链表没有交点，返回 null.
     * 在返回结果后，两个链表仍须保持原有的结构。
     * 可假定整个链表结构中没有循环。
     * 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
     * 例如：
     * l1：0,9,1,2,4
     * l2：    3,2,4
     * 返回：2
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int lenA = getListLen(headA);
        int lenB = getListLen(headB);
        if (lenA > lenB) {
            for (int i = 0; i < lenA - lenB; i++) {
                headA = headA.next;
            }
        } else if (lenA < lenB) {
            for (int i = 0; i < lenB - lenA; i++) {
                headB = headB.next;
            }
        }
        ListNode result = null;
        while (headA != null && headB != null) {
            if (headA.val == headB.val) {
                if (result == null) {
                    result = headA;
                }
            } else {
                result = null;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return result;
    }

    /**
     * 复制链表，包括next指针和random指针
     */
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node node = new Node(head.val);
        Node result = node;
        Node temp = head;
        while (temp != null) {
            node.val = temp.val;
            if (temp.next != null) {
                node.next = new Node(temp.next.val);
            }
            temp = temp.next;
            node = node.next;
        }
        temp = head;
        node = result;
        while (temp != null) {
            if (temp.random == null) {
                node.random = null;
            } else {
                Node temp2 = head;
                Node node2 = result;
                while (temp2 != null) {
                    if (temp.random == temp2) {
                        node.random = node2;
                        break;
                    } else {
                        temp2 = temp2.next;
                        node2 = node2.next;
                    }
                }
            }
            temp = temp.next;
            node = node.next;
        }
        return result;
    }

    private int getListLen(ListNode headA) {
        int len = 0;
        while (headA != null) {
            len++;
            headA = headA.next;
        }
        return len;
    }
}
